|
In the study of algorithms, an LP-type problem (also called a generalized linear program) is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem. ==Definition== LP-type problems were defined by as problems in which one is given as input a finite set of elements, and a function that maps subsets of to values from a totally ordered set. The function is required to satisfy two key properties: *Monotonicity: for every two sets , ''f''(''A'') ≤ ''f''(''B'') ≤ ''f''(''S''). *Locality: for every two sets and every element in , if , then . A ''basis'' of an LP-type problem is a set with the property that every proper subset of has a smaller value of than itself, and the ''dimension'' (or ''combinatorial dimension'') of an LP-type problem is defined to be the maximum cardinality of a basis. It is assumed that an optimization algorithm may evaluate the function only on sets that are themselves bases or that are formed by adding a single element to a basis. Alternatively, the algorithm may be restricted to two primitive operations: a ''violation test'' that determines, for a basis and an element whether , and a ''basis computation'' that (with the same inputs) finds a basis of }. The task for the algorithm to perform is to evaluate by only using these restricted evaluations or primitives. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「LP-type problem」の詳細全文を読む スポンサード リンク
|